Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 114/115

Q: Every Directed Acyclic Graph has at least one sink vertex.
A. True
B. False
C. ...
D. ...
Solution: A sink vertex is a vertex which has an outgoing degree of zero.
Q: The topological sorting of any DAG can be done in ________ time.
A. cubic
B. quadratic
C. linear
D. logarithmic
Solution: Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.
Q: If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
A. Many Hamiltonian paths are possible
B. No Hamiltonian path is possible
C. Exactly 1 Hamiltonian path is possible
D. Given information is insufficient to comment anything
Solution: For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.
Q: What would be the output of the following C++ program if the given input is

0 0 0 1 1
0 0 0 0 1
0 0 0 1 0
1 0 1 0 0
1 1 0 0 0
 
#include 
using namespace std;
bool visited[5];
int G[5][5];
 
void fun(int i)
{
	cout<>G[i][j];
 
	for(int i=0;i<5;i++)
		visited[i]=0;
 
	fun(0);
		return 0;
}
A. 0 2 3 1 4
B. 0 3 2 4 1
C. 0 2 3 4 1
D. 0 3 2 1 4
Solution: Given Input is the adjacency matrix of a graph G, whereas the function ‘fun’ prints the DFS traversal.
Q: Which of the given statement is true?
A. All the Cyclic Directed Graphs have topological sortings
B. All the Acyclic Directed Graphs have topological sortings
C. All Directed Graphs have topological sortings
D. All the cyclic directed graphs hace non topological sortings
Solution: Cyclic Directed Graphs cannot be sorted topologically.
Q: For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?
A. True
B. False
C. ...
D. ...
Solution: If such vertices exists it means that the graph contains a cycle which contradicts the first part of the statement.
Q: What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
A. Depends on a Graph
B. Will always be zero
C. Will always be greater than zero
D. May be zero or greater than zero
Solution: Every Directed Acyclic Graph has a source and a sink vertex.
Q:  In which of the following does a Directed Acyclic Word Graph finds its application in?
A. String Matching
B. Number Sorting
C. Manipulations on numbers
D. Pattern Printing
Solution: A Directed Acyclic Word Graph is similar to suffix tree, it can be viewed as a Deterministic Finite Automata.
Q: What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?
A. O(S1)
B. O(S2)
C. O(S1+S2)
D. O(1)
Solution: For each check of a word of length S1, we need to follow at most S1 edges.
Q: In which of the following case does a Propositional Directed Acyclic Graph is used for?
A. Representation of Boolean Functions
B. String Matching
C. Searching
D. Sorting of number
Solution: A Propositional Directed Acyclic Graph is used to represent a boolean function.

You Have Score    /10